﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using eu.h8me.Parsing.ParserLib;

namespace eu.h8me.Parsing.LexerLib {

    // Regex set state.
    public class RegExSetState : IEnumerable<RegEx> {

        // Constants.
        private const int INITIAL_STATE = 0;

        // Data.
        private List<RegEx> _RegExes = new List<RegEx>();
        private object _Tag;
        private Dictionary<string, Tree> _NameSet;
        private bool _Inclusive;
        private RegEx.MatchEventType _Event;
        private bool _Finished;
        private int _StartState;
        private Dictionary<int, List<DFATransition>> _TransitionSet;
        private Dictionary<int, AcceptorSet> _Acceptors;

        // Constructor.
        internal RegExSetState(bool inclusive, Dictionary<string, Tree> nameset) {
            // Set up inclusive flag.
            _Inclusive = inclusive;
            _NameSet = nameset;
        }

        // Tag state.
        public object Tag {
            get {
                // Return tag.
                return _Tag;
            }
            set {
                // Set up tag.
                if( _Finished )
                    throw new ArgumentException("Trying to set tag after finish");
                _Tag = value;
            }
        }

        // Name set accessor.
        internal Dictionary<string, Tree> NameSet {
            get {
                // Return bound name-set.
                return _NameSet;
            }
        }

        // Defined names.
        public IEnumerable<string> DefinedNames {
            get {
                // Return list of defined names.
                return _NameSet.Keys;
            }
        }

        // Inclusive state.
        public virtual bool IsInclusive {
            get {
                // Return inclusive state.
                return _Inclusive;
            }
            set {
                // Set up inclusive state.
                if( _Finished )
                    throw new ArgumentException("Trying to set inclusive state after finish");
                _Inclusive = value;
            }
        }

        // EOI event.
        public event RegEx.MatchEventType EOIEvent {
            add {
                // Attach event.
                if( _Finished )
                    throw new ArgumentException("Trying to attach EOI event after finish");
                else if( value == null )
                    throw new ArgumentNullException("Trying to attach NULL EOI event");
                _Event += value;
            }
            remove {
                // Detach event.
                if( _Finished )
                    throw new ArgumentException("Trying to detach EOI event after finish");
                else if( value == null )
                    throw new ArgumentNullException("Trying to detach NULL EOI event");
                _Event -= value;
            }
        }

        // Finished callback.
        public bool IsFinished {
            get {
                // Return finished state.
                return _Finished;
            }
        }

        // Access transitions.
        internal Dictionary<int, List<DFATransition>> TransitionSet {
            get {
                // Return transition set.
                return _TransitionSet;
            }
        }

        // List regexes registered here.
        public IEnumerator<RegEx> GetEnumerator() {
            // Return enumeration.
            return _RegExes.GetEnumerator();
        }

        // List regexes registered here, untyped.
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Return enumeration.
            return _RegExes.GetEnumerator();
        }

        // Access acceptor set.
        internal Dictionary<int, AcceptorSet> Acceptors {
            get {
                // Return acceptors set.
                return _Acceptors;
            }
        }

        // Start state.
        internal int StartState {
            get {
                // Return start state.
                return _StartState;
            }
        }

        // Attach a regular expression with the default flags char.
        public RegEx Add(string re) {
            // Use default flags.
            return Add(re, '@');
        }

        // Attach a regular expression.
        public RegEx Add(string re, char flags) {
            // Check state.
            if( re == null )
                throw new ArgumentNullException("Invalid regular expression to add");
            else if( _Finished )
                throw new ArgumentException("Cannot add regex after finish");

            // Parse the regular expression and attach it.
            RegEx regex = new RegEx(re, flags, this, _NameSet);
            _RegExes.Add(regex);

            // Return regular expression object.
            return regex;
        }

        // Count accessor.
        public int Count {
            get {
                // Return regex count.
                return _RegExes.Count;
            }
        }

        // Specific regex accessor.
        public RegEx this[int idx] {
            get {
                // Return regex with the specified index.
                if( idx < 0 || _RegExes.Count <= idx )
                    throw new ArgumentOutOfRangeException("Invalid index for regular expression");
                return _RegExes[idx];
            }
        }

        // Finish callback.
        internal void Finish(List<string> warnings) {
            // Set finished state and set up set precedence.
            _Finished = true;
            for( int i = 0; i < _RegExes.Count; ++i )
                _RegExes[i].SetPrecedence = -i;
        }

        // Initialize state.
        internal void BuildDFA(RegExSetState set, List<string> warnings) {
            // Initialize list of nodes with local res.
            NFAStateSet start = new NFAStateSet();
            List<RegEx> testre = new List<RegEx>(_RegExes);
            Dictionary<RegEx, bool> accepts = new Dictionary<RegEx, bool>();

            // Attach start nodes of this state to regex and set up accept state.
            foreach( RegEx re in _RegExes ) {
                start.Add(re.Tree.StartNode);
                accepts[re] = false;
            }

            // Check whether this is an inclusive state. If so, add nodes from the base state.
            if( _Inclusive ) {
                // Add all regular expressions of set for test and set up additional start nodes.
                testre.AddRange(set._RegExes);
                foreach( RegEx re in set._RegExes ) {
                    start.Add(re.Tree.StartNode);
                    accepts[re] = false;
                }
            }

            // Initialize state stacks.
            Dictionary<NFAStateSet, int> states = new Dictionary<NFAStateSet, int>();
            int nextidx = INITIAL_STATE;
            _TransitionSet = new Dictionary<int, List<DFATransition>>();
            _Acceptors = new Dictionary<int, AcceptorSet>();

            // Set up initial state and initialize state stack to process.
            Stack<object> toprocess = new Stack<object>();
            int startidx = states[start] = nextidx++;
            toprocess.Push(start);
            toprocess.Push(startidx);
            while( toprocess.Count > 0 ) {
                // Fetch state to process and it's index.
                int idx = (int)toprocess.Pop();
                NFAStateSet state = (NFAStateSet)toprocess.Pop();

                // Set up transition table for state.
                _TransitionSet[idx] = new List<DFATransition>();
                foreach( NFATransition trans in state.Transitions() ) {
                    // Check whether we know target state.
                    int transidx;
                    if( !states.TryGetValue(trans.State, out transidx) ) {
                        // Create target.
                        states[trans.State] = transidx = nextidx++;
                        toprocess.Push(trans.State);
                        toprocess.Push(transidx);
                    }

                    // Insert transition.
                    _TransitionSet[idx].Add(new DFATransition(trans.Range, transidx));
                }

                // Set up acceptor for this expression.
                _Acceptors[idx] = new AcceptorSet();
                foreach( RegEx re in testre ) {
                    // Test whether state contains end node and add that.
                    if( state.Contains(re.Tree.EndNode) )
                        // Attach the new acceptor.
                        _Acceptors[idx].Add(re);
                }
            }

            // Check acceptors for matching all regexes.
            foreach( AcceptorSet acc in _Acceptors.Values ) {
                // Set acceptors as available.
                if( acc.Acceptor != null )
                    accepts[acc.Acceptor] = true;
                if( acc.NewlineAcceptor != null )
                    accepts[acc.NewlineAcceptor] = true;
            }

            // Loop over accepts, marking those that don't.
            foreach( KeyValuePair<RegEx, bool> isacc in accepts )
                if( !isacc.Value )
                    warnings.Add(String.Format("Regular expression {0} can never match on input", isacc.Key));
        }

        // Minimize built DFA.
        internal void MinimizeDFA(List<string> warnings) {
            // Construct sets of DFA state groups (with one set).
            Dictionary<int, int> stategrps = new Dictionary<int, int>();
            List<HashSet<int>> states = new List<HashSet<int>>();
            stategrps[-1] = -1;

            // Initialize state set.
            states.Add(new HashSet<int>(_TransitionSet.Keys));
            foreach( int state in _TransitionSet.Keys )
                stategrps[state] = 0;

            // Group accepting states.
            Dictionary<AcceptorSet, int> acceptorset = new Dictionary<AcceptorSet, int>();
            foreach( KeyValuePair<int, AcceptorSet> acc in _Acceptors ) {
                // Check whether we know an acceptor set.
                int accidx;
                if( !acceptorset.TryGetValue(acc.Value, out accidx) ) {
                    // Need to create a new set.
                    acceptorset[acc.Value] = accidx = states.Count;
                    states.Add(new HashSet<int>());
                }

                // Attach acceptor state to specified acceptor set.
                stategrps[acc.Key] = accidx;
                states[accidx].Add(acc.Key);
                states[0].Remove(acc.Key);
            }

            // Loop while we split groups.
            bool changed;
            do {
                // Initialize output state groups.
                Dictionary<int, int> newstategrps = new Dictionary<int, int>();
                List<HashSet<int>> newstates = new List<HashSet<int>>();
                newstategrps[-1] = -1;

                // Loop over current state groups, creating transitions and checking whether transitions overlap.
                changed = false;
                foreach( HashSet<int> stategrp in states ) {
                    // When the previous state group is empty, don't do anything.
                    if( stategrp.Count == 0 )
                        continue;
                    else if( stategrp.Count == 1 ) {
                        // It's a one element group; this won't be split anymore, just copy it.
                        foreach( int state in stategrp )
                            newstategrps[state] = newstates.Count;
                        newstates.Add(stategrp);
                        continue;
                    }

                    // Walk over the ranges defined by this state group.
                    Dictionary<int, HashSet<int>> target = null;
                    foreach( IEnumerable<KeyValuePair<int, int>> trans in Transitions(stategrp) ) {
                        // Initialize output hash.
                        target = new Dictionary<int, HashSet<int>>();
                        foreach( KeyValuePair<int, int> dst in trans ) {
                            // Check whether we know the target state set.
                            int set = stategrps[dst.Value];
                            HashSet<int> targetset;
                            if( !target.TryGetValue(set, out targetset) )
                                // Initialize it.
                                target[set] = targetset = new HashSet<int>();

                            // Store the state.
                            targetset.Add(dst.Key);
                        }

                        // Check whether we have more than one result group; if so, we're done with a split.
                        if( target.Count > 1 )
                            break;
                    }

                    // Loop output sets, inserting them into output and updating states.
                    Debug.Assert(target != null, "No transitions possible from DFA state?!");
                    changed |= target.Count > 1;
                    foreach( KeyValuePair<int, HashSet<int>> newgrp in target ) {
                        // Update state index.
                        foreach( int state in newgrp.Value )
                            newstategrps[state] = newstates.Count;
                        newstates.Add(newgrp.Value);
                    }
                }

                // Update states array with new one.
                stategrps = newstategrps;
                states = newstates;
            } while( changed );

            // Finalize the new transition and acceptor arrays.
            Dictionary<int, List<DFATransition>> transitions = new Dictionary<int, List<DFATransition>>();
            Dictionary<int, AcceptorSet> acceptors = new Dictionary<int, AcceptorSet>();
            for( int i = 0; i < states.Count; ++i ) {
                // Fetch representative state and initialize transition table copy.
                int repstate = states[i].ElementAt<int>(0);
                List<DFATransition> statetrans = transitions[i] = new List<DFATransition>();
                DFATransition lasttrans = null;
                foreach( DFATransition trans in _TransitionSet[repstate] ) {
                    // Check whether last transition merges.
                    if( lasttrans != null && lasttrans.Range[1] == trans.Range[0] &&
                        lasttrans.Destination == stategrps[trans.Destination] ) {
                        // Yes, merges.
                        lasttrans = new DFATransition(new Range(lasttrans.Range[0], trans.Range[1]), lasttrans.Destination);
                        continue;
                    }

                    // No, need to create new transition, attaching the (possible) pending one.
                    if( lasttrans != null )
                        statetrans.Add(lasttrans);
                    lasttrans = new DFATransition(trans.Range, stategrps[trans.Destination]);
                }

                // Check whether a last transition is pending.
                if( lasttrans != null )
                    statetrans.Add(lasttrans);

                // Check whether this is the "new" start state and/or an accepting state.
                if( states[i].Contains(INITIAL_STATE) )
                    _StartState = i;
                if( _Acceptors.ContainsKey(repstate) )
                    acceptors[i] = _Acceptors[repstate];
            }

            // Update new statesets.
            _TransitionSet = transitions;
            _Acceptors = acceptors;
        }

        // Construct transition sets for a set of states.
        private IEnumerable<IEnumerable<KeyValuePair<int, int>>> Transitions(HashSet<int> stategrp) {
            // Initialize sets.
            int baseval = CharRange.MIN_VALUE;
            Dictionary<int, int> idx = new Dictionary<int, int>();
            Dictionary<int, int> curstates = new Dictionary<int, int>();

            // Initialize the states.
            foreach( int state in stategrp ) {
                // Set up missing state.
                idx[state] = 0;
                curstates[state] = -1;
            }

            // Next values.
            int nextval;
            Dictionary<int, int> statechange = new Dictionary<int, int>();
            do {
                // Walk over contained ranges.
                nextval = CharRange.MAX_VALUE;
                statechange.Clear();
                foreach( int state in stategrp ) {
                    // Check whether this state is eligible.
                    int stateidx = idx[state];
                    if( 2 * _TransitionSet[state].Count == stateidx )
                        continue;

                    // Check whether the value is smaller than current next.
                    if( _TransitionSet[state][stateidx >> 1].Range[stateidx & 1] < nextval ) {
                        // Yes, mark this as a unique change point.
                        nextval = _TransitionSet[state][stateidx >> 1].Range[stateidx & 1];
                        statechange.Clear();
                        statechange[state] = _TransitionSet[state][stateidx >> 1].Destination;
                    } else if( _TransitionSet[state][stateidx >> 1].Range[stateidx & 1] == nextval )
                        // Add this change point.
                        statechange[state] = _TransitionSet[state][stateidx >> 1].Destination;
                }

                // Check whether this value has data.
                if( baseval < nextval )
                    yield return curstates;

                // Update current states.
                baseval = nextval;
                foreach( KeyValuePair<int, int> newstate in statechange ) {
                    // Check what update this does.
                    if( ( idx[newstate.Key]++ & 1 ) == 1 ) {
                        // Remove state.
                        Debug.Assert(curstates[newstate.Key] != -1, "Removing state but does not contain state?");
                        curstates[newstate.Key] = -1;
                    } else {
                        // Add the state.
                        Debug.Assert(curstates[newstate.Key] == -1, "Adding state, but contains state?");
                        curstates[newstate.Key] = newstate.Value;
                    }
                }
            } while( baseval != CharRange.MAX_VALUE );
        }

        // EOI event signal.
        internal Token EOIExecute(RegExSet set, Grammar gram, Lexer lexer, Parser parser, int start) {
            // Execute a match.
            if( _Event != null )
                return _Event(new LexState(set, gram, this, lexer, parser, null, start), null);

            // No match event bound, return that.
            return null;
        }
    
    }

    // Set of regular expressions.
    public sealed class RegExSet : RegExSetState {

        // Data.
        private Dictionary<string, RegExSetState> _SubStates = new Dictionary<string, RegExSetState>();
        private List<string> _Warnings;

        // Constructor.
        public RegExSet()
            : base(false, new Dictionary<string, Tree>()) {
            // No specific construction.
        }

        // Inclusive state.
        public override bool IsInclusive {
            set {
                // Check state.
                if( IsFinished )
                    throw new ArgumentException("Trying to set inclusive state after finish");
                else if( value )
                    throw new ArgumentException("Can never set RegExSet to be inclusive");
            }
        }

        // State access.
        public RegExSetState this[string name] {
            get {
                // Check arguments.
                if( name == null )
                    throw new ArgumentNullException("Invalid exception name, is null");

                // Fetch state.
                RegExSetState state;
                if( !_SubStates.TryGetValue(name, out state) ) {
                    // Not defined; define it.
                    if( IsFinished )
                        throw new ArgumentException("Cannot define state after finish");
                    _SubStates[name] = state = new RegExSetState(false, NameSet);
                }

                // Return state.
                return state;
            }
        }

        // Definition with default flags char.
        public void Define(string name, string re) {
            // Add definition with default flags char.
            Define(name, re, '@');
        }

        // Definition of a regex expression.
        public void Define(string name, string re, char flags) {
            // Define a regex name.
            if( name == null || re == null )
                throw new ArgumentNullException("Invalid exception name or regex, is null");
            else if( IsFinished )
                throw new ArgumentException("Trying to define exception after finish");

            // Parse the regex and insert its tree into our cache.
            NameSet[name] = RegExParser.Parse(re, flags, true, NameSet);
        }

        // Finishing.
        public List<string> Finish() {
            // Check whether we are finished.
            if( IsFinished )
                return _Warnings;

            // Initialize state, finishing this and all substates.
            _Warnings = new List<string>();
            base.Finish(_Warnings);
            foreach( RegExSetState state in _SubStates.Values )
                state.Finish(_Warnings);

            // Build DFA states.
            base.BuildDFA(this, _Warnings);
            base.MinimizeDFA(_Warnings);
            foreach( RegExSetState state in _SubStates.Values ) {
                state.BuildDFA(this, _Warnings);
                state.MinimizeDFA(_Warnings);
            }

            // Return warnings.
            return _Warnings;
        }

        // Fetch lexer.
        public Lexer Lexer {
            get {
                // Check whether state is set up.
                if( !IsFinished )
                    throw new ArgumentException("Cannot start lexer when not finished");
                return new Lexer(this);
            }
        }

    }

}
